package zhiyou100.homework;

import java.util.Arrays;

public class shellSort {
    //希尔排序是插入排序的改良版,也称为缩小增量排序
    //先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
    public static void main(String[] args) {

        int[] arr = {7, 3, 1, 9, 5, 4, 2, 8, 6, 10};
        int temp;
        //选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；  这里是delta  5.. 2.. 1
        //通过增量将元素两两分组，对每组使用直接插入排序算法排序；增量逐渐减少，当增量减至1时，整个数据恰被分成一组，最后进行一次插入排序，整个数组就有序了。
        //按增量序列个数k，对序列进行 k 趟排序。 这里即3趟排序 。增量delta,通过delta来划分出不同的子序列,delta不断减少,划分的子序列更多
        for (int delta = arr.length / 2; delta >= 1; delta /= 2) {
            //这里通过外层循环得到不同的delta
            System.out.println("delta:" + delta);

            //分开的每一个子序列进行插入排序
            for (int i = delta; i < arr.length; i++) {

                for (int j = i; j >= delta && arr[j] < arr[j - delta]; j -= delta) {
                    //元素交换
                    temp = arr[j - delta];
                    arr[j - delta] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println("排序后" + Arrays.toString(arr));
        }
    }
}
